import string
class Solution:
    # @param beginWord, a string
    # @param endWord, a string
    # @param wordDict, a set<string>
    # @return an integer

    def ladderLength(self, beginWord, endWord, wordDict):
        def edit_distance1_set(word):
            return set(
                a + c + b[1:]
                for a, b in [(word[:i], word[i:]) for i in range(len(word) + 1)]
                for c in string.lowercase if b)

        def distance(wa, wb):
            count = 0
            for i in range(len(wa)):
                if wa[i] != wb[i]:
                    count += 1
            return count

        def next_words(word, lst):
            """return a candidates list of word's next transform"""
            return edit_distance1_set(word).intersection(lst)

        if not isinstance(wordDict, set):
            wordDict = set(wordDict)
        if distance(beginWord, endWord) == 1:
            return 2

        landing_zone = next_words(endWord, wordDict) # end while entering this zone

        if not landing_zone:
            return 0
        explore = set([beginWord])
        remain = wordDict - explore
        depth = 2
        while not (landing_zone.intersection(explore)):
            # print explore
            if not remain:
                return 0
            # print 'depth:{}, '.format(depth), explore
            old_explore = explore
            explore = set()
            for w in old_explore:
                explore.update(next_words(w, remain))
            if not explore:
                return 0
            remain.difference_update(explore)
            depth += 1
        # print explore, landing_zone
        return depth